//设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。 
//
// 请实现 KthLargest 类： 
//
// 
// KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 
// int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。 
// 
//
// 
//
// 示例： 
//
// 
//输入：
//["KthLargest", "add", "add", "add", "add", "add"]
//[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
//输出：
//[null, 4, 5, 5, 8, 8]
//
//解释：
//KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
//kthLargest.add(3);   // return 4
//kthLargest.add(5);   // return 5
//kthLargest.add(10);  // return 5
//kthLargest.add(9);   // return 8
//kthLargest.add(4);   // return 8
// 
//
// 
//提示：
//
// 
// 1 <= k <= 10⁴ 
// 0 <= nums.length <= 10⁴ 
// -10⁴ <= nums[i] <= 10⁴ 
// -10⁴ <= val <= 10⁴ 
// 最多调用 add 方法 10⁴ 次 
// 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素 
// 
//
// Related Topics 树 设计 二叉搜索树 二叉树 数据流 堆（优先队列） 👍 419 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class KthLargest {

    private minHeap heap;
    public KthLargest(int k, int[] nums) {
      heap=  new minHeap(k);
        for (int i = 0; i < nums.length ; i++) {
            add(nums[i]);
        }
    }
    
    public int add(int val) {
        if(!heap.isFull()){
            heap.offer(val);
        }else if(val>heap.peek()){
            heap.replace(val);
        }
        return heap.peek();
    }

    class minHeap{
        private int size=0;
        private int [] arry;

        public minHeap(int capacity) {
            arry=new int[capacity];
        }

        public int peek(){
            return arry[0];
        }

        public boolean isFull(){
            return size==arry.length;
        }

        public Boolean offer(int offered){
           if(size==arry.length){
               return false;
           }
           up(offered);
           size++;
           return true;
        }

        public void up(int offered){
            int child=size;
            while(child>0){
                int parent=(child-1)/2;
                if(offered<arry[parent]){
                    arry[child]=arry[parent];
                }else{
                    break;
                }
                child=parent;
            }
            arry[child]=offered;
        }

        public void down(int parent){
            int left=parent*2+1;
            int right=left+1;
            int min=parent;

            if(left<size&&arry[min]>arry[left]){
                min=left;
            }
            if(right<size&&arry[min]>arry[right]){
                min=right;
            }
            if(min!=parent){
                swap(min,parent);
                down(min);
            }
        }


        public void replace(int replaced){
            arry[0]=replaced;
            down(0);
        }

        public void swap(int i,int j){
            int tem=arry[i];
            arry[i]=arry[j];
            arry[j]=tem;
        }

    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */
//leetcode submit region end(Prohibit modification and deletion)
